﻿#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void Print(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

//int GetMidi(int* a, int begin, int end)
//{
//	int midi = (begin + end) / 2;
//	if (a[end] > a[begin])
//	{
//		if (a[end] < a[midi])
//		{
//			return end;
//		}
//		else
//		{
//			if (a[begin] > a[midi])
//				return begin;
//			else
//				return midi;
//		}
//	}
//	if (a[end] < a[begin])
//	{
//		if (a[end] > a[midi])
//		{
//			return end;
//		}
//		else
//		{
//			if (a[begin] < a[midi])
//				return begin;
//			else
//				return midi;
//		}
//	}
//}
int GetMidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	// begin midi end 三个数选中位数
	if (a[begin] < a[midi])
	{
		if (a[midi] < a[end])
			return midi;
		else if (a[begin] > a[end])
			return begin;
		else
			return end;
	}
	else // a[begin] > a[midi]
	{
		if (a[midi] > a[end])
			return midi;
		else if (a[begin] < a[end])
			return begin;
		else
			return end;
	}
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int left = begin ;
	int right = end;
	Swap(&a[begin], &a[(begin + end) / 2]);
	int keyi = begin;
	while (left < right)
	{
		while (left < right && a[right] > a[keyi])
		{
			right--;
		}
		while (left < right && a[left] < a[keyi])
		{
			left++;
		}
		
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	QuickSort(a, begin, left - 1);
	QuickSort(a, left + 1, end);

}
int main()
{
	int a[] = { 2,5,3,9,6,8,7,1,10 };
	int len = sizeof(a) / sizeof(a[0]);
	Print(a, len);
	QuickSort(a, 0, len-1);
	Print(a, len);
	srand(time(0));
	int N = 10;
	int* a1 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
		a1[i]=rand();
	}
	int begin5 = clock();
	QuickSort(a1, 0, N-1);
	int end5 = clock();
	for (int i = 0; i < N; i++)
	{
		printf("%d  ", a1[i]);
	}
	printf("\n");
	printf("QuickSortTime: %d\n", end5 - begin5);
	return 0;
}